1. Technical Field of the Invention
This invention relates to a resource management system and method. More particularly, it relates to a reusable integer pool for managing access to any reusable resource, including, but not limited to, data channels, data buffers, hardware status bits and logical connections.
2. Background Art
This invention addresses a class of problems that occur in either device driver or application program design. This class of problems can be identified by the following set of characteristics:
1. A limited number of resources of some type are available to the program which cannot be used by more than one user simultaneously. Permission to use such a resource must be obtained before attempting to use it. PA1 2. The permission to use a resource is a "ticket" for a specific resource only (i.e., buffer #1, or program #5, or channel #2, etc.) PA1 3. The maximum number of possible requesters exceeds the maximum available resources (otherwise, permanent assignment of a resource to each requester could be made thereby obviating the entire problem and this solution). PA1 1. Precious buffer space is consumed by the pointer variable 112, 122 that must be allotted in each buffer area. This space exists only to manage the linked list and serves no other useful purpose with respect to the actual use of the buffer. For larger numbers of data buffers, with pointers that might consume 4 bytes each, this can add up. PA1 2. Depending upon the underlying hardware and operating system architecture (e.g., OS/2, Windows NT), these pointers 112, 122 may be what are known as "far" pointers. Far pointers are pointers to memory that lies in another memory segment. Accessing data in a far segment consumes additional CPU cycles since segment registers must be reloaded, and when this is done, a variety of hardware checks are performed "under the covers" to validate the new segment access.
The resource(s) in question can be one of a wide variety of typical system resources. This background will focus on two such areas of application: (1) buffers in main storage on an adapter, and (2) status register bits. Inasmuch as the prior art approaches are different given the specifics of the problem, there is a need in the art to provide a single common approach that is superior to each specific prior art approach.
Application developers often use data buffer areas as sources or targets of operations such as direct memory access (DMA). In many cases, buffers cannot be allocated on-the-fly. This might be for performance reasons, due to limited storage capacity, or because buffers for DMA operations must be in a specific physical address location. In such a case, some number of buffer areas must be prepared for later use. These buffers must then be tracked or managed as they are doled out, used, and then returned by a subprocess to be available for use by another. This management is essential to prevent errors that would occur if more than one thread or process attempted to utilize the same buffer simultaneously.
Referring to FIGS. 1 and 2, the prior art approach is to allocate an array of such data buffers and to chain them together in the form of a linked list 108. In this case there are four available buffers 114, 116, 118, 120. Referring to FIG. 1, the variable "free-list" 110 is a pointer to first buffer 114. Each buffer area, in turn, has a pointer 112, 115, 117, 119 to the next available buffer. The final buffer 120 in the chain has a pointer value 122 of 0 indicating the end of list. When a data buffer is requested, free-list pointer 110 is consulted. If it is non-zero, a buffer is available. The pointer to it is "given" to the requesting process (it now has access to that buffer) and the free-list variable is updated to point to the next available buffer.
Referring to FIG. 2, the state of list 108 following this operation is shown. First buffer 114 is in use by a process, and free list pointer 110 now points 113 to next buffer area 116, which is now the first available buffer in list 108. Operation continues with processes requesting buffers (and receiving access to them) so long as there are free buffers. When a process is finished using a buffer, it returns it to the list in an process which is the inverse of that used to obtain a buffer. The "next" pointer 112 in the buffer structure 114 being returned is updated with the current free-list pointer 113, and the free.sub.-- list pointer 110 is updated with the address 111 of the buffer 114 being returned.
There are several drawbacks to this approach, as follows:
Access of data through far pointers is often a simple necessity, but the prior art method which employs a list 108 of far memory structures 114, 116, 118, 120 via a chain of pointers 111, 115, 117, 119 requires the manipulation of far memory pointers simply to manage the list. Consequently, there is a need in the art for a system and method which requires no far memory manipulations until the buffer is actually to be accessed.
A recurring problem in device driver or application software development is the need to manage or otherwise track the use of a limited number of serially re-useable resources. Serially re-useable implies that the resource is not consumed or otherwise destroyed by its use (it is `returned` when its use is finished) and, most significantly, implies that the resource may not be used by more than one user at a time.
A device driver design often encounters this type of problem when controlling an adapter that provides facilities for performing a requested operation and, on completion of the operation, the adapter informs the requester by setting a status bit in a register. Assuming a 32-bit architecture, the adapter may have 32 individual status bits for reporting completion status on up to 32 individual operations at a time. In order to distinguish between an operation completed for one requester versus that performed and completed for another, the device driver must assign a unique completion status bit in a bit-mapped status register for a given requester (and must be looking for the setting of that specific status bit and no other). Finally, when the requested operation is complete, the status bit (likely distinguished by its integer bit number) must be made available for reuse by some other requester as there might be more total requesters than available bits.
Referring to FIG. 3, a 32-bit "status" register is shown. Each bit 134, 136, 138 in bit positions 00-31 in register 130 indicates the completion status of a certain operation. For example, a number of bits 134, 138, etc., are "set", indicating the completion status of processes (or requests) corresponding to status bit positions 132 of 31, 24-26, 13-16, 11, 4-7, and 0-2. Thus, an adapter may be able to handle multiple outstanding requests to perform an operation, and it reports the completion status by setting a bit 134, 138, etc., in status register 130 corresponding to that request.
For multiple requests to be tracked, there must be a mechanism for uniquely assigning bits to requests and reusing the bits when the current request is completed. Referring further to FIG. 3, the common approach to this problem is to keep a shadow copy of status register 130 having bit positions 132, setting a bit 134 in the shadow when that status bit number is passed out to a requesting process, and clearing a bit 136 when the bit is no longer needed. The inefficiency in this approach is that shadow register must be scanned each time another process requests a status bit 134, 136 for use. This scanning is typically performed by shifting the shadow and testing the least significant bit position 00 139 to see if it is zero. If it is, then the number of shifts performed yields the status bit that can be used. In a steady state case, where bits are being "checked out" and returned at random intervals, approximately 16 such shift and test operations will be required, on the average, to find a free, available status bit. In the worst case, 32 shift and test operations will be required to determine that there is no bit available for use. There is, therefore, a need in the art for a system and method for checking out and returning N individual bits without requiring up to N shift and test operations.
Application designs can also encounter this class of problem. Suppose a multi-threaded application program has a limited number of data buffers for use in some type of operation (e.g. for reading data from a disk, or receiving messages from a network). As in the device driver register bits case, there may be more application threads than there are available data buffers. In this case each thread must obtain exclusive, temporary, use of a data buffer and, when finished, free it for use by another thread.
Both the device driver status bit and application data buffer problems are exactly the same: there exists a limited set of N resources which can be described by the set of integers 0 through N-1 (or 1 through N) and there are more than N users of said resource. Prior to using the resource, a unique integer index must be obtained which cannot be used simultaneously by more than one user, and which must be made available for use by others when the current operation is completed.
There are several solutions to this type of problem--these solutions differ according to the exact circumstances of the problem. That is, the `standard` solution to the device driver status bit problem is not the same as the standard solution to the application data buffer problem.
Consequently, there is a need in the art for a system and method that provides a unique, highly efficient alternative that may be applied to any such problem, regardless of specific circumstances, that may be accurately described as requiring a unique selection from the integers 0 through N-1.
U.S. Pat. No. 5,432,908 by M. Heddes, et al. provides for managing a set of reusable buffers. It uses a linked list-like technique for tracking free buffers and a set of rules for determining whether a request can be filled. Heddes only manages a set of buffers, uses an allocated buffer linked list, and the management entities are implemented as concurrently operating hardware units. There is, consequently, a need in the art for a resource management system and method which deals with any reusable resource, including data channels, data buffers, hardware status bits, logical connections; which does so without the use of linked lists or pointers; and which implements the rules by which a pool of integers is accessed with a small set of state variables and routines not requiring additional special hardware.
It is an object of the invention to provide an improved system and method for managing reusable system resources.
It is an object of the invention to provide an improved system and method for managing buffers in main storage.
It is an object of the invention to provide an improved method for managing storage on an adapter.
It is an object of the invention to provide an improved method for managing status register bits.
It is an object of the invention to provide an improved and single common approach for managing diverse system resources, including but not limited to buffers in main storage, storage on adapters, and status register bits.
It is an object of the invention to provide an improved system and method for managing buffers in main storage which requires no far memory manipulations until the buffer is actually to be accessed.
It is an object of the invention to provide an improved method for managing the selection of unique bits from among the integers 0 through N-1 or, alternatively, from among the integers 1 through N.
It is an object of the invention to provide a system and method for checking out and returning N individual bits without requiring up to N shift and test operations.
Finally, it is an object of the invention to provide a resource management system and method which deals with any reusable resource, including data channels, data buffers, hardware status bits, logical connections; which does so without the use of linked lists or pointers; and which implements the rules by which a pool of integers is accessed with a small set of state variables and routines not requiring additional special hardware.